package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 两个回文子序列长度的最大乘积
 */

public class Code2002 {
    public static void main(String[] args) {
        String s = "leetcodecn";
        System.out.println(new Code2002().maxProduct(s));
    }

    private int ans = 1;

    public int maxProduct(String s) {
        char[] chars = s.toCharArray();
        backtrace(chars, 0, new ArrayList<>(), new ArrayList<>());
        return ans;
    }

    private void backtrace(char[] chars, int index, List<Character> list1, List<Character> list2) {
        if (index == chars.length) {
            if (isPalindrome(list1) && isPalindrome(list2)) ans = Math.max(ans, list1.size() * list2.size());
            return;
        }

        backtrace(chars, index + 1, list1, list2);

        list1.add(chars[index]);
        backtrace(chars, index + 1, list1, list2);
        list1.remove(list1.size() - 1);

        list2.add(chars[index]);
        backtrace(chars, index + 1, list1, list2);
        list2.remove(list2.size() - 1);
    }

    private boolean isPalindrome(List<Character> list) {
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (list.get(left) != list.get(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}
